package Array;

/**
 * 209. 长度最小的子数组
 *给定一个含有 n 个正整数的数组和一个正整数 target 。
 *找出该数组中满足其总和大于等于 target 的长度最小的 连续
 * 子数组
 *  [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 *  解题思路：采用滑动窗口的思路， 动态地更新滑动窗口的左右边界，使得滑动窗口的值大于等于Target
 *  具体步骤：
 *      1：定义两个指针i 和 j，分别代表滑动窗口的左右边界，初始化值均为0
 *      2： 用 j指针不断扩大滑动窗口，直到j大于数组长度或者滑动窗口的和大于等于target
 *      3： 如果滑动窗口的和大于等于target，则记录当前滑动窗口的长度，并继续扩大滑动窗口，直到j大于数组长度或者滑动窗口的和小于target
 *      4： 重复步骤2和3，直到j大于数组长度
 *      5： 返回最小的滑动窗口长度
 */
public class MinSubArrayLen {

    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if(n==0){
            return 0;
        }
        // 滑动窗口边界
        int i=0,j=0;
        // 滑动窗口的和
        int sum=0;
        // 结果
        int resMin = Integer.MAX_VALUE;

        while(j<n){
            sum += nums[j];
            // 如果滑动窗口的和大于等于target，则记录当前滑动窗口的长度,并更新i值左边界
            while (sum >= target){
                resMin = Math.min(resMin, j-i+1);
                // 移动i值前，要从sum中减去
                sum -= nums[i];
                i++;
            }
            j++;
        }
        return resMin == Integer.MAX_VALUE ? 0 : resMin;
    }
}
